In approximate string matching (also known as the string-to-string correction problem), a similarity measure called the edit distance needs to be computed between two strings. This distance is computed using three editing operations, substitution, deletion and insertion. Each of these operations has a cost associated with it. The objective of approximate string matching is to determine the minimum cost required to transform one string into another using these three editing operations.
String comparison is an important task in many disciplines. It has applications in information retrieval, pattern recognition, error correction, molecular genetics, and text search and edit systems. Recent advances in Very Large Scale Integration (VLSI) technology have made the development of special purpose circuit structures for complex, computationally intensive tasks possible. High packaging densities, decrease in gate delays, decreasing fabrication costs, powerful CAD design automation tools, and reliable and fault-tolerant design strategies are some of the advantages of present day VLSI technology. The attributes of parallelism, concurrency, pipelining, modularity and regularity have become standard features of special purpose hardware designs. VLSI solutions often represent inexpensive implementations for high-performance designs.